home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / OUT-EDGE.C < prev    next >
C/C++ Source or Header  |  1992-01-02  |  17KB  |  461 lines
  1. /*****************************************************************************
  2. *   Routines to    test all edges for visibility relative to the global polygon *
  3. * list,    and output the visible ones, to    graphics screen    or as text file         *
  4. *                                         *
  5. * Written by:  Gershon Elber                Ver 2.0, Jan. 1989   *
  6. *****************************************************************************/
  7.  
  8. #ifdef __MSDOS__
  9. #include <conio.h>
  10. #endif /* __MSDOS__ */
  11.  
  12. #include <stdio.h>
  13. #include <math.h>
  14. #include <setjmp.h>
  15. #include <time.h>
  16. #include <ctype.h>
  17. #include <string.h>
  18. #include "program.h"
  19. #include "genmat.h"
  20. #include "iritprsr.h"
  21.  
  22. #define    MAX_POLYLINE_SIZE    50     /* Maximum size of output polyline. */
  23. #define EDGE_ON_PLANE_EPS     -0.003  /* Epsilon considers edge on plane. */
  24.  
  25. static EdgeStruct *OutEdgeHashTable[EDGE_HASH_TABLE_SIZE];
  26.  
  27. static void SaveCurrentMat(void);
  28. static void OutputEdge(EdgeStruct *PEtemp);
  29. static void EmitOutEdgeHashTable(void);
  30. static char *Real2Str(RealType R);
  31. static EdgeStruct *FoundMatchEdge(int *Colinear, EdgeStruct *PEdge);
  32. static int FuzzSamePoints(RealType Pt1[3], RealType Pt2[3]);
  33. static int ColinearPoints(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3]);
  34. static int VisibleEdge(int EdgeMinY, EdgeStruct *PEdge,
  35.                     IPPolygonStruct *PolyHashTable[]);
  36. static int VisibleEdgeOnePoly(EdgeStruct *PEdge, IPPolygonStruct *PPoly);
  37. static int InverseMatrix(MatrixType A);
  38.  
  39. /*****************************************************************************
  40. * Routine to test for visibility all edges in EdgeHashTable and    display    or   *
  41. * output the visible ones only.    It is assumed that only    totally    visible    or   *
  42. * invisible edges are in table (Pass 3 broke all other kind of edges).         *
  43. *****************************************************************************/
  44. void OutVisibleEdges(void)
  45. {
  46.     int    i;
  47.     long SaveTime = time(NULL);
  48.     EdgeStruct *PEtemp, *PEtail;
  49.  
  50.     fprintf(stderr, "\nPass 4, Edges [%5d] =      ", EdgeCount);
  51.     for (i = 0; i < EDGE_HASH_TABLE_SIZE; i++) OutEdgeHashTable[i] = NULL;
  52.     if (!InverseMatrix(GlblViewMat)) {
  53.     fprintf(stderr,
  54.             "\nNo inverse for matrix transformation, output is in screen space\n");
  55.     GenUnitMat(GlblViewMat);         /* No inverse transform at all. */
  56.     }
  57.     printf("Automatic Hidden Line generator\t\tGershon Elber\t\tJan. 1989\n");
  58.  
  59.     EdgeCount =    0;
  60.  
  61.     /* Output the viewing matrices. */
  62.     SaveCurrentMat();
  63.  
  64.     /* Output the OBJECT keyword line: */
  65.     printf("[OBJECT [COLOR %d] Hidden\n", HIDDEN_COLOR);
  66.  
  67.     for (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)
  68.     if ((PEtemp = EdgeHashTable[i]) != NULL)/* If any edge in that list. */
  69.         while (PEtemp) {
  70.         EdgeCount++;
  71.         fprintf(stderr, "\b\b\b\b\b%5d", EdgeCount);
  72.         PEtail = PEtemp    -> Pnext;       /* OutputEdge destroy it. */
  73.         if ((!PEtemp -> Internal || GlblInternal) &&
  74.             VisibleEdge(i, PEtemp, PolyHashTable))
  75.             OutputEdge(PEtemp);
  76.         PEtemp = PEtail;
  77.         }
  78.  
  79.     EmitOutEdgeHashTable();                /* Output all polylines. */
  80.     printf("]\n");                 /* Close the Hidden object. */
  81.     fprintf(stderr, ",  %d seconds.", time(NULL) - SaveTime);
  82. }
  83.  
  84. /*****************************************************************************
  85. * Routine to save current view trans. IritPrsrViewMat to a generic mat file  *
  86. *****************************************************************************/
  87. static void SaveCurrentMat(void)
  88. {
  89.     int    i, j;
  90.  
  91.     printf("[OBJECT MATRICES\n    [OBJECT VIEW_MAT\n\t[MATRIX");
  92.     for (i = 0; i < 4; i++) {
  93.     printf("\n\t    ");
  94.     for (j = 0; j < 4; j++) printf("%12lf ", IritPrsrViewMat[i][j]);
  95.     }
  96.     printf("\n\t]\n    ]\n");
  97.  
  98.     if (IritPrsrWasPrspMat) {
  99.     printf( "    [OBJECT PRSP_MAT\n\t[MATRIX");
  100.     for (i = 0; i < 4; i++) {
  101.         printf("\n\t    ");
  102.         for (j = 0; j < 4; j++) printf("%12lf ", IritPrsrPrspMat[i][j]);
  103.     }
  104.     printf("\n\t]\n    ]\n");
  105.     }
  106.  
  107.     printf("]\n\n");
  108. }
  109.  
  110. /*****************************************************************************
  111. * Routine to output one    edge to    the OutEdgeHashTable.                 *
  112. * The edge is inserted into OutEdgeHashTable to    be able    to match it into     *
  113. * the longest path possible - connecting edges into edge sequence.         *
  114. * Each edge is inserted    by its Ymin, which will    cause the paths    be in         *
  115. * increased Y order...                                 *
  116. *****************************************************************************/
  117. static void OutputEdge(EdgeStruct *PEtemp)
  118. {
  119.     int    Level;
  120.  
  121.     Level = (int) ((PEtemp -> Vertex[0]    -> Coord[1] + 1.0) *
  122.                             EDGE_HASH_TABLE_SIZE2);
  123.     PEtemp -> Pnext = OutEdgeHashTable[Level];
  124.     OutEdgeHashTable[Level] = PEtemp;
  125. }
  126.  
  127. /*****************************************************************************
  128. * Routine to scan the OutEdgeHashTable,    and Emit the longest paths found in  *
  129. * it by    searching for consecutive edges    and combining colinear edges.         *
  130. *****************************************************************************/
  131. static void EmitOutEdgeHashTable(void)
  132. {
  133.     int    i, j, Colinear, Count;
  134.     RealType Vec[MAX_POLYLINE_SIZE][3];
  135.     EdgeStruct *PEtemp, *PEnext;
  136.  
  137.     for    (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)     /* Scan all the hash table. */
  138.     while (OutEdgeHashTable[i]) {         /* Scan all edges in entry. */
  139.         PEtemp = OutEdgeHashTable[i];      /* Take edge out of table. */
  140.         OutEdgeHashTable[i]    = OutEdgeHashTable[i] -> Pnext;
  141.  
  142.         /* Print first vertices of polyline: */
  143.         Count = 0;
  144.         MultVecby4by4(Vec[Count++], PEtemp -> Vertex[0] -> Coord,
  145.                                 GlblViewMat);
  146.         MultVecby4by4(Vec[Count++], PEtemp -> Vertex[1] -> Coord,
  147.                                 GlblViewMat);
  148.  
  149.         while ((PEnext = FoundMatchEdge(&Colinear, PEtemp)) != NULL) {
  150.         if (Colinear)                /* Overwrite last entry. */
  151.             MultVecby4by4(Vec[Count - 1], PEnext -> Vertex[1] -> Coord,
  152.                                 GlblViewMat);
  153.         else
  154.             MultVecby4by4(Vec[Count++], PEnext -> Vertex[1] -> Coord,
  155.                                 GlblViewMat);
  156.         if (Count >= MAX_POLYLINE_SIZE) break;
  157.         PEtemp = PEnext;
  158.         }
  159.  
  160.         printf("    [POLYLINE %d\n", Count);
  161.         for (j = 0; j < Count; j++)
  162.         printf("\t[%s %s %s]\n",
  163.             Real2Str(Vec[j][0]),
  164.             Real2Str(Vec[j][1]),
  165.             Real2Str(Vec[j][2]));
  166.  
  167.         printf("    ]\n");
  168.     }
  169. }
  170.  
  171. /*****************************************************************************
  172. * Convert a real number into a string.                         *
  173. * The routine mentains 3 different buffers simultanuously so up to 3 calls   *
  174. * can be issued from same printf...                         *
  175. *****************************************************************************/
  176. static char *Real2Str(RealType R)
  177. {
  178.     static int i = 0;
  179.     static char Buffer[3][LINE_LEN_LONG];
  180.     int j, k;
  181.  
  182.     if (ABS(R) < 1e-6) R = 0.0;            /* Round off very small numbers. */
  183.  
  184.     sprintf(Buffer[i], "%-8.6lg", R);
  185.  
  186.     for (k = 0; !isdigit(Buffer[i][k]) && k < LINE_LEN_LONG; k++);
  187.     if (k >= LINE_LEN_LONG) {
  188.     fprintf(stderr, "Conversion of real number failed.\n");
  189.     MyExit(3);
  190.     }
  191.  
  192.     for (j = strlen(Buffer[i]) - 1; Buffer[i][j] == ' ' && j > k; j--);
  193.     if (strchr(Buffer[i], '.') != NULL)
  194.     for (; Buffer[i][j] == '0' && j > k; j--);
  195.     Buffer[i][j+1] = 0;
  196.  
  197.     j = i;
  198.     i = (i + 1) % 3;
  199.     return Buffer[j];
  200. }
  201.  
  202. /*****************************************************************************
  203. * Routine to scan the OutEdgeHashTable for a match edge    if any,    delete it    *
  204. * from HashTable and return it.    if colinear with PEdge set Colinear to TRUE. *
  205. * return FALSE if no match found (end of polyline).                 *
  206. *****************************************************************************/
  207. static EdgeStruct *FoundMatchEdge(int *Colinear, EdgeStruct *PEdge)
  208. {
  209.     int    Level;
  210.     EdgeStruct *PEtemp, *PElast;
  211.  
  212.     Level = (int) ((PEdge -> Vertex[1] -> Coord[1] + 1.0) *
  213.                             EDGE_HASH_TABLE_SIZE2);
  214.     PEtemp = PElast = OutEdgeHashTable[Level];
  215.     while (PEtemp) {                /* First scan for colinear edge. */
  216.     if (FuzzSamePoints(PEdge -> Vertex[1] -> Coord,
  217.                PEtemp -> Vertex[0] -> Coord) &&
  218.         ColinearPoints(PEdge -> Vertex[0] -> Coord,
  219.                PEdge -> Vertex[1] -> Coord,
  220.                PEtemp -> Vertex[1] -> Coord)) {
  221.         *Colinear =    TRUE;
  222.         /* Delete that edge    from hash table    structure: */
  223.         if (PEtemp == PElast)
  224.         OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
  225.         else
  226.         PElast -> Pnext = PEtemp -> Pnext;
  227.  
  228.         if (FuzzSamePoints(PEtemp -> Vertex[0] -> Coord,
  229.                    PEtemp -> Vertex[1] -> Coord))
  230.         return FoundMatchEdge(Colinear, PEdge); /* Call recursively! */
  231.         else
  232.             return PEtemp;
  233.     }
  234.     PElast = PEtemp;
  235.     PEtemp = PEtemp    -> Pnext;
  236.     }
  237.  
  238.     PEtemp = PElast = OutEdgeHashTable[Level];
  239.     while (PEtemp) {                /* Next scan for any match edge. */
  240.     if (FuzzSamePoints(PEdge -> Vertex[1] -> Coord,
  241.                PEtemp -> Vertex[0] -> Coord)) {
  242.         *Colinear =    FALSE;
  243.         /* Delete that edge    from hash table    structure: */
  244.         if (PEtemp == PElast)
  245.          OutEdgeHashTable[Level] = OutEdgeHashTable[Level] -> Pnext;
  246.         else PElast    -> Pnext = PEtemp -> Pnext;
  247.  
  248.         if (FuzzSamePoints(PEtemp -> Vertex[0] -> Coord,
  249.                    PEtemp -> Vertex[1] -> Coord))
  250.         return FoundMatchEdge(Colinear, PEdge); /* Call recursively! */
  251.         else
  252.         return PEtemp;
  253.     }
  254.     PElast = PEtemp;
  255.     PEtemp = PEtemp    -> Pnext;
  256.     }
  257.  
  258.     return NULL;                  /* No match - end of polyline. */
  259. }
  260.  
  261. /*****************************************************************************
  262. * Routine to test if two points    are almost the same, and returns TRUE if so. *
  263. *****************************************************************************/
  264. static int FuzzSamePoints(RealType Pt1[3], RealType Pt2[3])
  265. {
  266.     return (APX_EQ(Pt1[0], Pt2[0]) &&
  267.         APX_EQ(Pt1[1], Pt2[1]) &&
  268.         APX_EQ(Pt1[2], Pt2[2]));
  269. }
  270.  
  271. /*****************************************************************************
  272. * Routine to test if three points are colinear,    and returns TRUE if so...    *
  273. * Algorithm: cross product should be zero if colinear...             *
  274. * Note this routine does not return TRUE if Pt2    is not between Pt1..Pt3.     *
  275. *****************************************************************************/
  276. static int ColinearPoints(RealType Pt1[3], RealType Pt2[3], RealType Pt3[3])
  277. {
  278.     int    i;
  279.     RealType Xout, Yout, Zout, U[3], V[3], temp;
  280.  
  281.     for    (i = 0; i < 3; i++) {
  282.     U[i] = Pt2[i] -    Pt1[i];
  283.     V[i] = Pt3[i] -    Pt2[i];
  284.     }
  285.     temp = sqrt(SQR(U[0]) + SQR(U[1]) + SQR(U[2]));
  286.     if (APX_EQ(temp, 0.0)) return TRUE;
  287.     for    (i = 0; i < 3; i++) U[i] = U[i] / temp;
  288.  
  289.     temp = sqrt(SQR(V[0]) + SQR(V[1]) + SQR(V[2]));
  290.     if (APX_EQ(temp, 0.0)) return TRUE;
  291.     for    (i = 0; i < 3; i++) V[i] = V[i] / temp;
  292.  
  293.     /* Xoutput = Uy * Vz - Uz *    Vy. */
  294.     Xout = U[1]    /* Uy */  * V[2] /* Vz */  -
  295.        U[2]    /* Uz */  * V[1] /* Vy */;
  296.  
  297.     /* Youtput = Uz * Vx - Ux *    Vz. */
  298.     Yout = U[2]    /* Uz */  * V[0] /* Vx */  -
  299.        U[0]    /* Ux */  * V[2] /* Vz */;
  300.  
  301.     /* Zoutput = Ux * Vy - Uy *    Vx. */
  302.     Zout = U[0]    /* Ux */  * V[1] /* Vy */  -
  303.        U[1]    /* Uy */  * V[0] /* Vx */;
  304.  
  305.     return APX_EQ(Xout, 0.0) && APX_EQ(Yout, 0.0) && APX_EQ(Zout, 0.0) &&
  306.        ((MIN(Pt1[0], Pt3[0]) < Pt2[0]) && (MAX(Pt1[0], Pt3[0]) > Pt2[0]) &&
  307.         (MIN(Pt1[1], Pt3[1]) < Pt2[1]) && (MAX(Pt1[1], Pt3[1]) > Pt2[1]));
  308. }
  309.  
  310. /*****************************************************************************
  311. * Routine to test the visibility of the    given edge relative to all polygons  *
  312. * in polygon list. return TRUE if the edge is visible. It is assumed that    *
  313. * the edge is whole visible or whole invisible (Pass 3 broke the edge if     *
  314. * that whas not    true). Also it is assumed the polygons are all convex.         *
  315. * A short cut is made to test the edge only against the    needed polygons         *
  316. * only, using the polygon hash table and Y level sorting.             *
  317. *****************************************************************************/
  318. static int VisibleEdge(int EdgeMinY, EdgeStruct * PEdge,
  319.                           IPPolygonStruct *PolyHashTable[])
  320. {
  321.     int    EdgeMaxY, i;
  322.     IPPolygonStruct *PPolyList, *PPolyLast;
  323.  
  324.     EdgeMaxY = MIN((MAX(PEdge -> Vertex[0] -> Coord[1],
  325.             PEdge -> Vertex[1] -> Coord[1]) + 1.0) *
  326.                         EDGE_HASH_TABLE_SIZE2,
  327.            EDGE_HASH_TABLE_SIZE1);
  328.  
  329.     /* Test the    edge only in the interval 0..EdgeMaxY as these are the only  */
  330.     /* which might hide    that edge. Also    polygons with MaxY less    than         */
  331.     /* EdgeMinY    are deleted from PolyHashTable as it is    assumed    the edges    */
  332.     /* are scanned in increasing order of the EdgeHashTable.             */
  333.     for    (i = 0; i <= EdgeMaxY; i++) {
  334.     PPolyList = PPolyLast =    PolyHashTable[i];
  335.     while (PPolyList) {
  336.         if ((PPolyList -> Ymax + 1.0) * EDGE_HASH_TABLE_SIZE2 < EdgeMinY)
  337.         /* Delete this polygon!    */
  338.         if (PPolyList == PPolyLast) {
  339.             PolyHashTable[i] = PPolyLast = PPolyList -> Pnext;
  340.             PPolyList =    PPolyList -> Pnext;
  341.         }
  342.         else {
  343.             PPolyList =    PPolyList -> Pnext;
  344.             PPolyLast -> Pnext = PPolyList;
  345.         }
  346.         else {         /* Polygon still active - test edge against it. */
  347.         /* If found one    polygon    that hides this    edge return FALSE... */
  348.  
  349.         if (!VisibleEdgeOnePoly(PEdge, PPolyList)) return FALSE;
  350.         PPolyLast = PPolyList;
  351.         PPolyList = PPolyList -> Pnext;
  352.         }
  353.     }
  354.     }
  355.  
  356.     return TRUE;
  357. }
  358.  
  359. /*****************************************************************************
  360. * Routine to test the visibility of the    given edge relative to one polygon   *
  361. * return TRUE if the edge is visible. It is assumed that the edge is whole   *
  362. * visible or whole invisible (Pass 3 broke the edge if that was not true).   *
  363. * Also it is assumed the polygons are all convex.                 *
  364. *****************************************************************************/
  365. static int VisibleEdgeOnePoly(EdgeStruct *PEdge, IPPolygonStruct *PPoly)
  366. {
  367.     int    i;
  368.     RealType MidPt[3];
  369.     IPVertexStruct *PList;
  370.  
  371.     for    (i = 0; i < 3; i++) MidPt[i] =        /* Calc a mid point on the edge: */
  372.         (PEdge -> Vertex[0] -> Coord[i] +
  373.          PEdge -> Vertex[1] -> Coord[i]) / 2.0;
  374.  
  375.     /* Test if edges is    out of polygon boundary    box: */
  376.     if (MidPt[0] > PPoly -> Xmax || MidPt[0] < PPoly ->    Xmin ||
  377.     MidPt[1] > PPoly -> Ymax || MidPt[1] < PPoly ->    Ymin) return TRUE;
  378.  
  379.     if (PPoly -> Plane[0] * MidPt[0] +
  380.     PPoly -> Plane[1] * MidPt[1] +
  381.     PPoly -> Plane[2] * MidPt[2] +
  382.     PPoly -> Plane[3] > EDGE_ON_PLANE_EPS)
  383.     return TRUE;                /* Edge in front of polygon. */
  384.  
  385.     /* We cannt    escape it - we now must    find if    the point is included in */
  386.     /* polygon area. We    assume the polygon is convex and use the fact     */
  387.     /* that the    polygon    list is    ordered    such that the cross product     */
  388.     /* of two consecutive vertices and the point is positive for all     */
  389.     /* consecutive vertices pairs iff the point    is in the polygon.     */
  390.     PList = PPoly -> PVertex;
  391.     while (PList -> Pnext) {
  392.     if (CrossProd(PList -> Coord, PList -> Pnext -> Coord, MidPt) < 0)
  393.         return TRUE;                  /* Out of polygon! */
  394.     PList =    PList -> Pnext;
  395.     }
  396.     /* Now test    last polygon edge (last    point, first point in poly list) */
  397.     if (CrossProd(PList -> Coord, PPoly -> PVertex -> Coord, MidPt) < 0)
  398.     return TRUE;                      /* Out of polygon! */
  399.  
  400.     return FALSE;
  401. }
  402.  
  403. /*****************************************************************************
  404. * Procedure to calculate the INVERSE of    a given    MatrixType matrix A which is *
  405. * modified to the inverted matrix. Return TRUE if inverse exists.         *
  406. *****************************************************************************/
  407. static int InverseMatrix(MatrixType A)
  408. {
  409.     MatrixType InvA;
  410.     int    i, j, k;
  411.     RealType V, D;
  412.  
  413.     GenUnitMat(InvA);
  414.  
  415.     for    (i = 0; i < 4; i++) {
  416.     V = A[i][i];                      /* Find the new pivot. */
  417.     k = i;
  418.     for (j = i + 1; j < 4; j++) if (A[j][i] > V) {
  419.         /* Find maximum on col i, row i+1..4. */
  420.         V =    A[j][i];
  421.         k =    j;
  422.     }
  423.     j = k;
  424.  
  425.     if (i != j) for    (k = 0; k < 4; k++) {
  426.         /* Swap. */
  427.         D = A[i][k]; A[i][k] = A[j][k]; A[j][k] = D;
  428.         D = InvA[i][k]; InvA[i][k] = InvA[j][k]; InvA[j][k] = D;
  429.     }
  430.  
  431.     for (j = i + 1; j < 4; j++) {    /* Eliminate col i from row i+1..4. */
  432.         V =    A[j][i]    / A[i][i];
  433.         for    (k = 0; k < 4; k++)    {
  434.         A[j][k]       -= V    * A[i][k];
  435.         InvA[j][k] -= V    * InvA[i][k];
  436.         }
  437.     }
  438.     }
  439.  
  440.     for    (i = 4-1; i >= 0; i--) {               /* Back Substitution. */
  441.     if (A[i][i] == 0) return FALSE;                   /* Error. */
  442.  
  443.     for (j = 0; j < i; j++) {     /* Eliminate col i from row 1..i-1. */
  444.         V =    A[j][i]    / A[i][i];
  445.         for    (k = 0; k < 4; k++) {
  446.         /* A ->    [j][k] -= V * A[i][k]; */
  447.         InvA[j][k] -= V    * InvA[i][k];
  448.         }
  449.     }
  450.     }
  451.  
  452.     for    (i = 0; i < 4; i++)            /* Normalize the inverse Matrix. */
  453.     for (j = 0; j < 4; j++)
  454.         InvA[i][j] /= A[i][i];
  455.     for    (i = 0; i < 4; i++)               /* Copy inverted    matrix to A. */
  456.     for (j = 0; j < 4; j++)
  457.         A[i][j] = InvA[i][j];
  458.  
  459.     return TRUE;
  460. }
  461.